package may;

import java.lang.annotation.Target;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Set;

/**
 * @author ：冯涛滔
 * @date ：Created in 2020-5-24 19:46
 * @description：
 * @modified By：
 * @version:
 */
public class May24 {
    /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/count-square-submatrices-with-all-ones/ 统计全为一的正方形矩阵
     *动态规划写
     * 状态: 以当前的节点作为正方形的左上角  (大的正方形一定包含小的正方形 所以只要看当前节点可以形成多大的正方形即可)括号里的有空可以实现一下
     * 状态转移公式: i+size-1>=matrix.length||j+size-1>=matrix[h].length||matrix[h][j+k]!=1||matrix[i+k][l]!=1  符合条件的时候就证明以及不能形成更大的正方形了
     * 边界值: 数组为空
     * create time: 2020-5-24 19:47
     * @params [matrix]
     * @return int
     */
    public int countSquares(int[][] matrix) {
        if (matrix.length==0) {
            return 0;
        }
        int x = Math.min(matrix[0].length,matrix.length);
        int res = 0;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if(matrix[i][j]==1){
                    res++;//起码就形成了一个1边长的正方形
                    int l = j+1;//要检查的列
                    int h = i+1;//要检查的行
                    int size = 2;
                    boolean flag = true;
                    while(flag){
                        for (int k = 0; k < size; k++) {
                            if(i+size-1>=matrix.length||j+size-1>=matrix[h].length||matrix[h][j+k]!=1||matrix[i+k][l]!=1){
                                flag = false;
                                break;
                            }

                        }
                        if(flag){
                            size++;
                            l++;
                            h++;
                            res++;
                        }
                    }
                }
            }
        }
        return res;
    }
    /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/longest-arithmetic-sequence/ 最长等差数列
     * create time: 2020-5-24 21:15
     * @params [A]
     * @return int
     */
    public int longestArithSeqLength(int[] A) {
        if(A.length==0){
            return 0;
        }

        int max = 0;
        for (int i = 0; i <A.length-1 ; i++) {
            for (int j = i+1; j <A.length ; j++) {
                int c = A[i]-A[j];
                int size = 2;
                int number = A[j];
                for (int k = j+1; k < A.length; k++) {//在这里可以写成二分搜索 会快很多
                    if(number-A[k]==c){
                        number = A[k];
                        size++;
                    }
                max = Math.max(max,size);
                }
            }
        }

        return max;
    }
    /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/longest-string-chain/ 最长字符串链
     * 初始化 要先按照字符长度升序排序
     * 动态规划: 我们只需要关心当前这个单词可能是哪个单词的前生
     * create time: 2020-5-26 9:45
     * @params [words]
     * @return int
     */
    public int longestStrChain(String[] words) {
        Arrays.sort(words, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return o1.length() - o2.length();
            }
        });
        int[] dp = new int[words.length];
        int res = 0;
        for (int i = 0; i < words.length; i++) {
            for (int j = i+1; j < words.length; j++) {
                if(isPredecessor(words[i],words[j])){
                    dp[j] = Math.max(dp[j],dp[i]+1);
                    res = Math.max(res,dp[j]);
                }
            }
        }
        return res+1;
    }
    /**
     * 判断a是否是b的前身 是返回true 如 "bda" 是"bdca"的前身
     *
     * @param a
     * @param b
     * @return
     */

    private boolean isPredecessor(String a, String b) {
        int i = 0, j = 0;
        int m = a.length(), n = b.length();
        if ((m + 1) != n) return false;
        while (i < m && j < n) {
            if (a.charAt(i) == b.charAt(j)) i++;
            j++;
        }
        return i == m;
    }
    public static void main(String[] args) {
        int[][] list = {{0,1,1,1},
        {1,1,1,1},
        {0,1,1,1}};
        May24 a = new May24();
        System.out.println(a.countSquares(list));
        int[] q = {20,1,15,3,10,5,8};
        System.out.println(a.longestArithSeqLength(q));

    }
}
